Memoization

Memoization is a technique used to speed up function calls by caching their results. The results can be cached only if the function is pure, meaning that it has no side effects or outputs and that it does not depend on any global state.

Memoizing `sin` function#

A trivial function that can be memoized is the sine function sin.

import math
_SIN_MEMOIZED_VALUES = {}
def memoized_sin(x):
  if x not in _SIN_MEMOIZED_VALUES:
    _SIN_MEMOIZED_VALUES[x] = math.sin(x)
  return _SIN_MEMOIZED_VALUES[x]
print('memoized_sin(1): ', memoized_sin(1))
print('_SIN_MEMOIZED_VALUES:', _SIN_MEMOIZED_VALUES)
print('memoized_sin(2):', memoized_sin(2))
print('memoized_sin(2):', memoized_sin(2))
print('_SIN_MEMOIZED_VALUES:', _SIN_MEMOIZED_VALUES)
print('memoized_sin(1):', memoized_sin(1))
print('_SIN_MEMOIZED_VALUES:', _SIN_MEMOIZED_VALUES)

Enter to Rename, Shift+Enter to Preview

Basic memoization implementation

The first time that memoized_sin is called with an argument that is not stored in _SIN_MEMOIZED_VALUES, the value will be computed and stored in this dictionary. Later on, if we call the function with the same value again, the result will be retrieved from the dictionary rather than being computed another time. While sin is a function that computes very quickly, this may not be true for some advanced functions involving more complicated computations.

Usage of memoization can be simplified in Python by using a decorator. PyPI lists a few implementations of memoization through decorators, from very simple cases to the most complex and comprehensive.

`functools`#

Starting with Python 3.3, the functools module provides a LRU (least recently used) cache decorator. This decorator provides the same functionality as the memoization described here, but with the benefit that it limits the number of entries in the cache, removing the least recently used one when the cache size reaches its maximum.

The module also provides statistics on cache hits, misses, etc. In my opinion, these are must-haves when implementing such a cache. There’s no point in using memoization, or any caching technique if you are unable to meter its usage and usefulness.

In the example below, you can see the implementation of the memoized_sin() function, using functools.lru_cache.

import functools
import math
@functools.lru_cache(maxsize=2)
def memoized_sin(x):
  return math.sin(x)
print('memoized_sin(2): ', memoized_sin(2))
print('Cache info: ', memoized_sin.cache_info())
print('memoized_sin(2): ', memoized_sin(2))
print('Cache info: ', memoized_sin.cache_info())
print('memoized_sin(3): ', memoized_sin(3))
print('Cache info: ', memoized_sin.cache_info())
print('memoized_sin(4): ', memoized_sin(4))
print('Cache info: ', memoized_sin.cache_info())
print('memoized_sin(3): ', memoized_sin(3))
print('Cache info: ', memoized_sin.cache_info())
memoized_sin.cache_clear()
print('Cache info: ', memoized_sin.cache_info())

Enter to Rename, Shift+Enter to Preview

Using functools.lru_cache

Enter to Rename, Shift+Enter to Preview

Using cachetools for memoization

Memoizing sin function#

functools#

Using cachetools for memoization#

Memoizing `sin` function#

`functools`#

Using `cachetools` for memoization#